package leetcode100;

// TODO 变异的二分法 【-】 搜索旋转排序数组
// TODO https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-er-fen-92jot/
// TODO 由于要求时间复杂度 logn, 所以自然联想到 二分法

public class lc100_0033 {

    public int search(int[] nums, int target) {
        // 注：从左到右三段: A段、B段、C段
        int left = 0, right = nums.length-1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return mid;

            if (nums[mid] >= nums[left]) {
                // mid 在左边
                if (target < nums[mid] && target >= nums[left]) {
                    // traget 在mid左边 (A段)
                    right = mid - 1;
                } else {
                    // target 在mid右边 (B段 或 C段)
                    left = mid + 1;
                }
            } else {
                // mid 在右边
                if (target > nums[mid] && target <= nums[right]) {
                    // traget 在mid右边 (C段)
                    left = mid + 1;
                } else {
                    // target 在mid左边 (A段 或 B段)
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

}